/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package mergesort;

import java.util.ArrayList;

/**
 *
 * @author Student
 */
public class MergeSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        ArrayList<Integer> m = new ArrayList();
        InitArray(m);
        print(m);
        m = Merge_Sort(m);
        print(m);
    }

    private static ArrayList<Integer> Merge_Sort(ArrayList<Integer> m) {
        if (m.size() <= 1) {
            return m;
        } else {
            ArrayList<Integer> left = new ArrayList();
            ArrayList<Integer> right = new ArrayList();
            int middle = m.size() / 2;
            for (int i = 0; i < middle; i++) {
                left.add(m.get(i));
            }
            for (int i = middle; i < m.size(); i++) {
                right.add(m.get(i));
            }
            left = Merge_Sort(left);
            right = Merge_Sort(right);
            return Merge(left, right);
        }
    }

    private static void InitArray(ArrayList<Integer> m) {

        for (int i = 0; i < 1000000; i++) {
            m.add((int) (Math.random() * 100));
        }

    }

    private static ArrayList<Integer> Merge(ArrayList<Integer> left, ArrayList<Integer> right) {
        ArrayList<Integer> result = new ArrayList();
        while (left.size() > 0 || right.size() > 0) {
            if (left.size() > 0 && right.size() > 0) {
                if (left.get(0) < right.get(0)) {
                    result.add(left.get(0));
                    left.remove(0);
                } else {
                    result.add(right.get(0));
                    right.remove(0);
                }
            } else if (left.size() > 0) {
                result.add(left.get(0));
                left.remove(0);
            } else if (right.size() > 0) {
                result.add(right.get(0));
                right.remove(0);
            }
        }
        return result;
    }

    private static void print(ArrayList<Integer> m) {
        for (int i = 0; i < m.size(); i++) {
            System.out.print(m.get(i) + " ");
        }
        System.out.println("");
    }
}
